#include <stdio.h>

void merge(int *arr, int left, int right, int mid, int *tmparr) 
{   //合并
    int pos = left;
    int l_pos = left; //左边第一个
    int r_pos = mid +1; //右边第一个
    while (l_pos <= mid && r_pos <= right) {
        if (arr[l_pos] < arr[r_pos]) {
            tmparr[pos++] = arr[l_pos++];
        } else {
            tmparr[pos++] = arr[r_pos++];
        }
    }
    while (l_pos <= mid) {
        tmparr[pos++] = arr[l_pos++];
    }
    while (r_pos <= mid) {
        tmparr[pos++] = arr[r_pos++];
    }
    //tmp数组拷贝到原数组
    while (left <= right)
    {
        arr[left] = tmparr[left];
        left++;
    }
}

void merge_sort(int *arr, int left, int right, int *tmparr) 
{
    if (left < right) {
        int mid = (left +right)/2;
        //递归
        merge_sort(arr, left, mid, tmparr);
        merge_sort(arr, mid+1, right, tmparr);
        //do something
        merge(arr, left, right, mid, tmparr);
    }
}

int main(void)
{
    int arr[10] = {10, 9, 5, 8, 6, 7, 4, 3, 2, 1};
    int len = sizeof(arr) / sizeof(arr[0]);

    int tmparr[10]; //临时数组
    merge_sort(arr, 0, len-1, tmparr); //归并排序
    //打印
    for (int i = 0; i < len ; i++) {
        printf("%d ", arr[i]);
    }
    putchar('\n');
    return 0;
}